The present invention relates to message dispatch in object-oriented systems. More specifically, the invention relates to site specific message dispatch techniques for the Java(trademark) virtual machine.
The fundamental idea behind object-oriented languages is the combination of both data and the methods (or functions) that operate on that data into a single unit, which is called an object. An object""s functions typically provide the only way to access the data that is encapsulated by the object. The data is accessed by sending a message to the object instructing the object to invoke the method specified by the message.
Efficient message dispatch is of paramount importance in object-oriented languages. This is because message dispatch is a very frequent operation in objectoriented programs and is performed at runtime; therefore, it should be as fast as possible. Message dispatch, however, is far from being a trivial operation. Unlike procedural programming languages (e.g., the C programming language) that can determine a function""s address before runtime, object-oriented languages must determine the method that handles a message that has been dispatched to a receiver object at runtime, and it may involve an extensive search.
In order to better understand the complexities of message dispatch, FIG. 1 shows a class hierarchy including methods of each class. A class hierarchy 1 includes at its root a parent class A 3 that defines two virtual functions foo() and bar(). Virtual functions are functions that may be defined in a parent class and redefined in the children classes. Classes B 5 and class C 7 inherit the data and methods of the parent class A. As shown, class B does not redefine either of the virtual functions foo() and bar(). However, class C redefines the virtual function foo. When an object of class C is requested to invoke the method foo, the method invoked will be the method defined by the class C, not the parent class A. Classes D 9 and E 11 also redefine the method foo.
As it is generally impossible to determine the class of an object statically, the search for the correct method is performed at runtime, during message dispatch. There are many known techniques for implementing method dispatch. For example, FIG. 2 shows an inline cache. Assume a method 51 was originally as follows:
main()
{
. . .
x.foo();
. . .
}
Thus, the method main includes a statement x.foo() in order to invoke the method foo of object x.
During runtime, the system would have to determine to which class object x belongs before the method to handle the method could be invoked. With an inline cache, the first time the system determines the class to which object x belongs, a direct call to the class""s method is written into the computer code.
Assuming that object x is a member of class A, the call x.foo() is changed to a direct call A::foo(). The arrow specifies a method foo for class A 53. Since the object x may not be of class A every time, a prolog 55 verifies that the object x is of the correct class, which is represented as the expression x=A meaning that it is determined if the class of object x is equal to class A. The class of an object may be determined from a value stored in the object. If the object is of the correct class, a jump is performed to method code 57 that handles the message.
Returning to prolog 55, if the object is not of class A, a method lookup routine is called in order to determine the correct method. Once the correct method is found, the system updates the message dispatch (or call) site with a direct call to that method. Additionally, the system updates the prolog to specify the new class. As an example, assume that the first time that the system encountered x.foo (), object x was of class A and the data structures were modified as shown in FIG. 2.
Once the data structures are modified as shown, subsequent calls to x.foo() will be substantially more efficient if object x is of class A. However, if object x subsequently is of class B, prolog 55 calls a method lookup routine to find the method and let""s assume it determines that object x of now is class B. Referring again to FIG. 1, it is seen that the method foo for class B is the same method foo as defined in class A (i.e., class B did not redefine the virtual function foo). Accordingly, the message dispatch in method 51 will be changed to B::foo () and the condition in prolog 55 will be changed to x=B.
An inline cache may be an efficient way of implementing message dispatch if the object at a call site bar remains the same class. However, if the object is of multiple classes, the system is continually calling the method lookup routine and patching the call site and prolog. Thus, the system may be actually less efficient.
Another technique for implementing message dispatch is the use of polymorphic inline cache as shown in FIG. 3. As before, a method 101 originally included a method dispatch x.foo(). With a polymorphic inline cache, a stub 103 is generated that is able to perform the message dispatch for different receiver types. The original message dispatch is overwritten with a call to the polymorphic inline cache stub 103. Each time a new receiver type is encountered, a statement is added to the stub. As shown, three different receiver types of have been encountered thus far. If the receiver type and has been encountered, a call is made to the method to handle the message for that receiver type. Otherwise, the method lookup routine is called to determine the appropriate method to handle the message. Typically, a new statement will be added to stub 103 in order to handle each new receiver type.
The polymorphic inline cache is more flexible than the inline cache as it is able to handle multiple receiver types. However, a drawback of the polymorphic inline cache is that as more receiver types are encountered, the stub continues to grow and it becomes less and less efficient at performing message dispatch. For example, the system may need to plow through multiple if statements before finding the right method to handle the message.
FIG. 4 shows another message dispatch technique called hashing. In hashing, the original message dispatch in a method 151, x.foo(), is overwritten with a call to a hash function 153. The hash function hashes the receiver type and the message in order to form a hash key, which is typically an index into a hash table 155. The hash table includes an index 157, receiver types 159, messages 161, and methods 163. Once the hash function hashes to a row in cash table 155, the receiver type and message are retrieved from columns 159 and 161 of the hash table. If the receiver type and message at the call site match the receiver type and message in the row of the hash table, the method specified in column 163 of hash table 155 is invoked. Otherwise, a method lookup routine is called in order to find the correct method. Typically, the new method is then added to the hash table.
Although hashing is the most flexible message dispatch technique we have described thus far, it is more computationally and storage intensive then the other techniques. Another drawback of the message dispatch techniques we have described is that none of the techniques are site specific. In other words, none of the message dispatch techniques provide the flexibility of handling message dispatches at different call sites in a different manner. Other method dispatch techniques are described in xe2x80x9cMessage Dispatch on Pipelined Processors,xe2x80x9d by K. Driesen et al., ECOOP, 1995, which is hereby incorporated by reference for all purposes.
Accordingly, there is a need for site specific message dispatch that is both efficient in terms of speed and computer code size. Additionally, there is a need for site specific message dispatch that is flexible and can adapt as the object-oriented program executes.
Embodiments of the present invention provide innovative site specific message dispatch techniques that may be efficient in terms of speed and computer code size. By providing sites specific message dispatch techniques, message dispatch may be optimized for each message dispatch site. Therefore, instead of attempting to find one message dispatch technique that is efficient for all call sites, the technique may be adjusted to better accommodate the specific site. Several embodiments of the invention are described below.
In one embodiment, the invention provides a method of implementing message dispatch in an object-oriented environment. A predicted receiver type is saved at a site wherein a message is dispatched to a receiver object. The message is then sent to the receiver object. Upon the receiver object receiving the message, it is verified that the receiver object is of the saved predicted receiver type. Typically, the predicted receiver type is saved into a register by a move instruction preceding the message dispatch instruction.
In another embodiment, the invention provides a method of implementing message dispatch in an object-oriented environment. A predicted receiver type is saved at a site where a message is dispatched to a receiver object. The message is then sent to the receiver object. Upon the receiver object receiving the message, it is verified that the receiver object is of the saved predicted receiver type. If the receiver object is not of the saved predicted receiver type, the predicted receiver type is changed to a type of the receiver object, a method lookup routine is called to obtain a new method, and the site is changed to invoke the new method.
In another embodiment, the invention provides a method of implementing message dispatch for an object-oriented program. A first message dispatch technique is performed at a specific site to dispatch messages to receiver objects. Dynamically during program execution, it is determined if a second message dispatch technique is desirable at the specific site. If the second message dispatch technique is desirable, the second message dispatch technique is performed at the specific site to dispatch messages to the receiver objects. In preferred embodiments, it is determined that the second message dispatch technique is desirable if the specific site has dispatched messages to more than a predetermined number of different receiver object types.
Other features and advantages of the invention will become readily apparent upon review of the following detailed description in association with the accompanying drawings.